#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <map>
#include <windows.h>
using namespace std;

#define SQRT_FORM true
#define E_FORM false
#define MAX_VAL 90000

/**
 * 判断一个数是否为完全平方数
 * @param n 待判断的数
 * @return 如果n是完全平方数则返回true，否则返回false
 */
bool is_square(double n) {
    // 计算n的平方根
    double sqrt_n = sqrt(n);
    // 判断平方根是否为整数
    return sqrt_n == floor(sqrt_n);
}


/*
 * @brief 通过 BFS 搜索从初始值 startNum 到目标值 inputNum 的最短变换路径，并输出路径和步数。
 *
 * 该函数模拟三种数学操作：
 * 1. x -> sqrt(x^2 + 1)，等价于两次变换；
 * 2. x -> sqrt(x^2 - 1)，等价于两次变换（要求 x >= 1）；
 * 3. x -> x^2，等价于一次变换。
 * 4. x -> sqrt(x)，等价于一次变换。
 * 5. x -> 2x，等价于三次变换。
 * (x -> e^x -> e^2x (ln)-> 2x)
 * 6. x -> x/2，等价于三次变换。
 * 7. x -> x/3，等价于三次变换。
 * note：通过将target平方以避免浮点数
 *
 * 使用广度优先搜索（BFS）寻找最少操作次数的路径，并打印路径过程。
 * @param startNum 起始值
 * @param inputNum 目标值
 * @param pathLimit 路径长度限制
 * @return pair<从初始值 startNum 到目标值的最短变换步数,变换过程>
 */

 // pair<int,vector<int>> solveFromStart(int startNum, int inputNum) {
 //     if (startNum == inputNum){
 //         vector<int> path;
 //         return make_pair(0, path);
 //     }
 //     // 将target平方以避免浮点数
 //     int target = inputNum * inputNum;
 //     int start = startNum * startNum;

 //     // 使用BFS查找最短路径
 //     // 由于涉及浮点数，我们使用map来记录访问过的状态
 //     unordered_map<int, pair<int, int>> parent; // {current: {parent, operation}}
 //     unordered_map<int, int> steps; //记录到达key的步骤数量
 //     queue<int> q;

 //     // 初始状态：从startNum出发
 //     q.push(start);
 //     steps[start] = 0;

 //     bool found = false;
 //     int min_steps = 0;
 //     int final_value = 0;

 //     while (!q.empty() && !found) {
 //         // 从队列前端取出当前状态进行处理
 //         int current = q.front();
 //         q.pop();

 //         // 寻找到达当前状态的步骤数
 //         int current_steps = steps[current];

 //         // 检查是否到达目标
 //         if (current == target) {
 //             found = true;
 //             min_steps = current_steps;
 //             final_value = current;
 //             break;
 //         }

 //         // 防止步骤过多或值过大
 //         if (current_steps > 1000 || current > 90000) {
 //             // 过大则处理下一个值
 //             continue;
 //         }

 //         // 操作一：x -> x + 1 (两次变换)
 //         // 相当于：x -> sqrt(x^2 + 1)
 //         int next1 = current + 1;
 //         if (steps.find(next1) == steps.end() || steps[next1] > current_steps + 2) {
 //             // step中未记录或步骤数比当前步骤数更大
 //             steps[next1] = current_steps + 2;
 //             parent.insert(make_pair(next1, make_pair(current, 1)));
 //             q.push(next1);
 //         }
 //         // x -> x - 1 (两次变换)
 //         // 相当于：x -> sqrt(x^2 - 1) (两次变换，要求x >= 1)
 //         if (current >= 1) {
 //             int next2 = current - 1;
 //             if ((steps.find(next2) == steps.end() || steps[next2] > current_steps + 2)) {
 //                 steps[next2] = current_steps + 2;
 //                 parent[next2] = { current, 2 };
 //                 q.push(next2);
 //             }
 //         }

 //         // 操作三：x -> x^2 (一次变换)
 //         int next3 = current * current;
 //         if (next3 <= 90000 && (steps.find(next3) == steps.end() || steps[next3] > current_steps + 1)) {
 //             steps[next3] = current_steps + 1;
 //             parent[next3] = { current, 3 };
 //             q.push(next3);
 //         }

 //         // 操作四：x -> sqrt(x) (一次变换)
 //         // 要求必须是完全平方数，否则操作无意义
 //         if (is_square(current)) {
 //             int next4 = (int)sqrt(current);
 //             if (next4 <= 90000 && (steps.find(next4) == steps.end() || steps[next4] > current_steps + 1)) {
 //                 steps[next4] = current_steps + 1;
 //                 parent[next4] = { current, 4 };
 //                 q.push(next4);
 //             }
 //         }


 //         // 操作五：a -> 4a (三次变换)
 //         // 相当于 x -> 2x (三次变换)
 //         int next5 = current * 4;
 //         if (next5 <= 90000 && (steps.find(next5) == steps.end() || steps[next5] > current_steps + 3)) {
 //             steps[next5] = current_steps + 3;
 //             parent[next5] = { current, 5 };
 //             q.push(next5);
 //         }


 //         //操作六：a -> a/4 (三次变换)
 //         if (current % 4 == 0) {
 //             int next6 = current / 4;
 //             if (next6 <= 90000 && (steps.find(next6) == steps.end() || steps[next6] > current_steps + 3)) {
 //                 steps[next6] = current_steps + 3;
 //                 parent[next6] = { current, 6 };
 //                 q.push(next6);
 //             }
 //         }

 //         /*
 //         //操作七：a -> a/9 (三次变换)
 //         if (current % 9 == 0) {
 //             int next7 = current / 9;
 //             if (next7 <= 90000 && (steps.find(next7) == steps.end() || steps[next7] > current_steps + 2)) {
 //                 steps[next7] = current_steps + 2;
 //                 parent[next7] = { current, 7 };
 //             }
 //         }
 //         */

 //     }

 //     // 重构路径
 //     vector<int> path;
 //     int current = final_value;

 //     while (parent.find(current) != parent.end()) {
 //         path.push_back(parent[current].second);
 //         current = parent[current].first;
 //     }

 //     return make_pair(min_steps, path);

 // }


 /**
  * Node结构体
  * 用于表示搜索过程中的状态节点
  * 包含节点的值、已花费的代价、状态以及优先队列的比较逻辑
  */
struct Node {
    int val;    // 平方后的值
    // val正负表示 form
    // SQRT_FORM > 0; E_FORM < 0
    // val = 0 一定不是最短路径，直接continue即可
    int cost;   // 已花代价
    /**
     * 重载小于运算符，用于优先队列的排序
     * 通过返回cost > o.cost实现小根堆的效果
     * @param o 与之比较的另一个Node对象
     * @return 如果当前节点代价大于另一个节点则返回true
     */
    bool operator<(const Node& o) const { return cost > o.cost; } // 小根堆
};
// 优先队列，用于存储待处理的节点，按照代价从小到大排序
priority_queue<Node> pq;
// 距离映射表，记录每个值对应的最小代价
unordered_map<int, int> minCosts;
// 前驱映射表，记录每个值的前驱值和操作编号
unordered_map<int, pair<int, int>> pre;


/**
 * @brief 松弛操作函数，用于更新节点间的最短路径
 *
 * 该函数实现 Dijkstra 算法中的松弛操作，通过比较当前路径和新路径的长度，
 * 来更新目标节点的最短距离和前驱节点信息。
 *
 * @param preNodeVal 前驱节点的值
 * @param nextNodeVal 后继节点的值
 * @param cost 从当前节点到后继节点的代价
 * @param operateNum 操作编号，用于记录路径信息
 */
void relax(int preNodeVal, int nextNodeVal, int cost, int operateNum) {
    // 计算通过当前节点到达下一节点的新距离
    int newCost = minCosts[preNodeVal] + cost;

    // 检查是否溢出
    if (newCost < 0) return;

    // 如果下一节点尚未访问过，或者新距离更短
    if (minCosts.find(nextNodeVal) == minCosts.end() || newCost < minCosts[nextNodeVal]) {
        // 更新下一节点的最短距离
        minCosts[nextNodeVal] = newCost;
        // 记录下一节点的前驱节点和对应操作
        pre[nextNodeVal] = { preNodeVal, operateNum };
        // 将下一节点加入优先队列
        pq.push({ nextNodeVal, newCost });
    }
}



/**
 * 使用 Dijkstra 算法寻找从 startNum 的平方到 targetNum 的平方的最短路径，
 * 并返回最短路径的代价和所使用的操作序列。
 *
 * 该函数模拟这些数学操作：
 * val > 0 (SQRT_FORM)
 * 1. x -> x + 1，等价于两次变换；
 * 2. x -> x - 1，等价于两次变换（要求 x >= 1）；
 * 3. x -> x^2，等价于一次变换。
 * 4. x -> sqrt(x)，等价于一次变换。
 *
 * val < 0 (E_FORM)
 * 5. x -> 4x，等价于一次变换。
 * 6. x -> x/4，等价于一次变换。
 * 7. x -> x/9，等价于一次变换。
 *
 * 8. SQRT_FORM -> E_FORM，等价于一次变换。
 * 9. E_FORM -> SQRT_FORM，等价于一次变换。
 * note：通过将target平方以避免浮点数
 *
 * @param startNum 起始数字，实际起始节点值为 startNum * startNum
 * @param targetNum 目标数字，实际目标节点值为 targetNum * targetNum
 * @return 返回一个 pair，first 为最短路径的代价，second 为逆序的操作序列（1~7 表示不同操作）
 *         如果无法到达目标节点，则返回 {-1, {}}
 */
pair<int, vector<int>> dijkstraPath(int startNum, int targetNum) {
    int startNodeVal = int(startNum) * startNum;
    int targetNodeVal = int(targetNum) * targetNum;

    minCosts.clear(); pre.clear();
    while (!pq.empty()) pq.pop();

    minCosts[startNodeVal] = 0;
    pq.push({ startNodeVal, 0 });

    // // 优先队列，用于存储待处理的节点，按照代价从小到大排序
    // priority_queue<Node> pq;
    // // 距离映射表，记录每个值对应的最小代价
    // unordered_map<int, int> minCosts;
    // // 前驱映射表，记录每个值的前驱状态和操作编号
    // unordered_map<int, pair<int, int>> pre;

    while (!pq.empty()) {
        // 每次从队列中取出的都是 cost 值最小的节点
        Node minCostNode = pq.top();
        pq.pop();

        int operateVal = minCostNode.val;
        int minCostNow = minCostNode.cost;
        if (operateVal == targetNodeVal) break;            // 已找到最短路径，提前退出
        if (minCostNow != minCosts[operateVal]) continue;   // 当前节点已经被更新过，跳过旧状态
        if (operateVal == 0) continue; // val = 0 一定不是最短路径，直接continue即可

        if (operateVal > 0) {
            // 操作 1: +1 （代价为 2）
            if (operateVal + 1 <= MAX_VAL)
                relax(operateVal, operateVal + 1, 2, 1);

            // 操作 2: -1 （代价为 2）
            if (operateVal - 1 >= 0)
                relax(operateVal, operateVal - 1, 2, 2);

            // 操作 3: 平方 （代价为 1）
            // 预检查，防止平方后 int 溢出
            if (operateVal <= (int)sqrt(MAX_VAL))
                relax(operateVal, operateVal * operateVal, 1, 3);

            // 操作 4: 开方 （代价为 1），仅当 operateVal 是完全平方数时可执行
            int rt = (int)sqrt(operateVal);
            if (rt * rt == operateVal)
                relax(operateVal, rt, 1, 4);

            // 操作 8: 转换为 E_FORM （代价为 1）
            relax(operateVal, -operateVal, 1, 8);
        }

        if (operateVal < 0) {
            // 操作 5: 乘以 4 （代价为 1）
            int m4 = operateVal * 4;
            if (-m4 <= MAX_VAL)
                relax(operateVal, m4, 1, 5);

            // 操作 6: 除以 4 （代价为 1），仅当 operateVal 可被 4 整除时可执行
            if (operateVal % 4 == 0)
                relax(operateVal, operateVal / 4, 1, 6);

            // 操作 7: 除以 9 （代价为 1），仅当 operateVal 可被 9 整除时可执行
            if (operateVal % 9 == 0)
                relax(operateVal, operateVal / 9, 1, 7);

            // 操作 9: 转换为 SQRT_FORM （代价为 1）
            relax(operateVal, -operateVal, 1, 9);
        }

    }

    if (!minCosts.count(targetNodeVal))               // 目标节点不可达
        return { -1, {} };

    // 回溯路径，构造操作序列
    vector<int> operationSequence;
    for (int currentVal = targetNodeVal; currentVal != startNodeVal; ) {
        auto [preVal, operationNum] = pre[currentVal];
        operationSequence.push_back(operationNum);
        currentVal = preVal;
    }

    return { minCosts[targetNodeVal], operationSequence };
}
pair<int, vector<int>> solveFromStart(int startNum, int inputNum) {
    // 调用Dijkstra算法计算从起始数字到目标数字的最短路径
    auto [d, path] = dijkstraPath(startNum, inputNum);
    return make_pair((int)d, path);
}

/**
 * @brief 根据给定的状态和次数对初始值进行变换，并输出相应的LaTeX格式表达式。
 *
 * 该函数根据 operationNum 的值选择不同的数学操作，对 preValue 进行 times 次变换，
 * 并在控制台输出变换过程和结果的 LaTeX 表达式。
 *
 * @param operationNum 状态码，决定执行哪种数学操作（1-9），见 dijkstraPath
 * @param times  执行操作的次数。
 * @param preValue 初始值，作为计算的起点。
 * @return 变换后的最终值。
 */
int print_status(int operationNum, int times, int preValue) {
    int value = preValue;

    // 根据状态码和次数对初始值进行多次变换得到输出值
    for (int i = 0; i < times; i++) {
        switch (operationNum) {
        case 1:
            value = value + 1;
            break;
        case 2:
            value = value - 1;
            break;
        case 3:
            value = value * value;
            break;
        case 4:
            value = (int)sqrt(value);
            break;

        case 5:
            value = value * 4;
            break;
        case 6:
            value = (int)value / 4;
            break;
        case 7:
            value = (int)value / 9;
            break;

        case 8:
            value = -value;
            break;
        case 9:
            value = -value;
            break;
        }
    }

    // 根据状态码输出对应的表示步骤的 LaTeX 格式表达式
    switch (operationNum) {
    case 1:
        cout << "\\xrightarrow{" << times << "次g_1} ";
        break;
    case 2:
        cout << "\\xrightarrow{" << times << "次g_2} ";
        break;
    case 3:
        if (times == 1) {
            cout << "\\xrightarrow{x^2} ";
        } else {
            cout << "\\xrightarrow{" << times << "次x^2} ";
        }
        break;
    case 4:
        if (times == 1) {
            cout << "\\xrightarrow{\\sqrt{}} ";
        } else {
            cout << "\\xrightarrow{" << times << "次\\sqrt{}} ";
        }
        break;

    case 5:
        if (times == 1) {
            cout << "\\xrightarrow{x^2} ";
        } else {
            cout << "\\xrightarrow{" << times << "次x^2} ";
        }
        break;
    case 6:
        if (times == 1) {
            cout << "\\xrightarrow{\\sqrt{}} ";
        } else {
            cout << "\\xrightarrow{" << times << "次\\sqrt{}} ";
        }
        break;
    case 7:
        if (times == 1) {
            cout << "\\xrightarrow{\\sqrt[3]{}} ";
        } else {
            cout << "\\xrightarrow{" << times << "次\\sqrt[3]{}} ";
        }
        break;

    case 8:
        if (times == 1) {
            cout << "\\xrightarrow{exp} ";
        } else {
            cout << "\\xrightarrow{" << times << "次exp} ";
        }
        break;
    case 9:
        if (times == 1) {
            cout << "\\xrightarrow{log} ";
        } else {
            cout << "\\xrightarrow{" << times << "次log} ";
        }
        break;
    }

    // 输出对应的最终值格式
    // SQRT_FORM
    if (value > 0) {
        if (is_square(value)) {
            cout << sqrt(value) << " ";
        } else {
            cout << "\\sqrt{" << value << "} ";
        }
    }
    // E_FORM
    else if (value < 0) {
        int outputVal = -value;
        if (is_square(outputVal)) {
            cout << "e^{" << sqrt(outputVal) << "} ";
        } else {
            cout << "e^{ \\sqrt{" << outputVal << "} } ";
        }
    }

    return value;
}

/**
 * 打印解决方案路径和步骤数
 * @param startNum 起始数字
 * @param inputNum 输入数字
 * @param min_steps 最小步骤数
 * @param path 解决方案路径
 * @return 返回最小步骤数
 */
int printSolution(int startNum, int inputNum, int min_steps, vector<int>& path) {
    // 输出步骤数
    cout << "$$ \n\\begin{flalign} \n& L(" << inputNum << ")" << " \\le " << min_steps << " & \\\\" << endl;
    if (path.empty()) {
        cout << "\\end{flalign} \n$$" << endl;
        return min_steps;
    }

    cout << "& " << startNum << " ";
    int value = startNum * startNum;
    int time = 1;

    // 输出路径（注意需要逆序输出）
    for (int i = path.size() - 1; i >= 0; i--) {
        int status = path[i];
        // 处理连续相同状态的合并输出
        if (i > 0 && path[i - 1] == path[i]) {
            time++;
            continue;
        } else {
            value = print_status(path[i], time, value);
            time = 1;
        }
    }
    cout << "& \\\\ \n\\end{flalign} \n$$" << endl;
    return min_steps;
}

/**
 * 求解从初始数字到目标数字的最优路径
 * @param inputNum 目标数字
 * @param triangular 是否使用三角函数，默认为true
 * @return 返回求解结果，并由printSolution函数输出
 */
int solve(int inputNum, bool triangular = true) {
    map<int, int> startNumSteps;
    // 预定义的起始数字及其对应的步数偏移量
    if (triangular) {
        map<int, int> startNums = { {1,1},{30,6},{45,2},{60,6},{90,1},{120,7},{135,6},{150,8},{180,3} };
        startNumSteps = startNums;
    } else {
        map<int, int> startNums = { {1,1} };
        startNumSteps = startNums;
    }

    // 初始化最小步数、最优起始数字和最优路径
    int minSteps = 10000;
    int minStartNum = 0;
    vector<int> minPath;

    // 遍历所有预定义的起始数字，寻找最优解
    for (auto& entry : startNumSteps) {
        int startNum = entry.first;
        int stepsAdd = entry.second;
        if (minSteps <= stepsAdd) {
            continue;
        }
        // 从当前起始数字求解到目标数字的路径
        pair<int, vector<int>> solveTmp = solveFromStart(startNum, inputNum);
        // 计算总步数（当前路径步数加上预定义偏移量）
        int steps = solveTmp.first + stepsAdd;
        // 更新最优解
        if (steps <= minSteps) {
            minSteps = steps;
            minPath = solveTmp.second;
            minStartNum = startNum;
        }
    }

    // 输出最终的解决方案
    return printSolution(minStartNum, inputNum, minSteps, minPath);
}

int main(int argc, char* argv[]) {
    SetConsoleOutputCP(65001); // 设置控制台输出编码为 UTF-8

    const bool USE_DEGREE = true;
    const bool USE_RADIAN = false;
    bool solveMode = USE_DEGREE;

    string modeArgString = "default";
    if (argc > 1) {
        modeArgString = argv[1];
    }
    if (modeArgString == "-radian") {
        cout << "弧度制解算，按回车继续..." << endl;
        cin.get();
        solveMode = USE_RADIAN;
    } else if (modeArgString == "-degree") {
        cout << "角度制解算，按回车继续..." << endl;
        cin.get();
        solveMode = USE_DEGREE;
    } else {
        cout << "解算模式：-radian 弧度制，-degree 角度制" << endl;
        cout << "现选择默认解算模式：角度制解算" << endl;
        cout << "角度制解算，按回车继续..." << endl;
        cin.get();
        solveMode = USE_DEGREE;
    }

    // 初始化累加器并执行循环计算
    // 从2到200依次调用solve函数并将结果累加到sum中
    int sum = 1;
    for (int i = 2; i <= 200; i++) {
        sum = sum + solve(i, solveMode);
    }

    cout << endl;
    cout << sum << endl;
    cout << "按下回车退出..." << endl;
    cin.get();
    return 0;
}


